package com.future;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Description:
 * 给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
 * <p>
 * 注意:
 * <p>
 * 输入只包含小写英文字母。
 * 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
 * 输入字符串的长度小于 50,000。
 * 示例 1:
 * <p>
 * 输入: "owoztneoer"
 * <p>
 * 输出: "012" (zeroonetwo)
 * 示例 2:
 * <p>
 * 输入: "fviefuro"
 * <p>
 * 输出: "45" (fourfive)
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/10/8 16:11
 */
public class Solution_originalDigits_423 {

    public static void main(String[] args) {
        String s = "owoztneoer";
        s = "zerozonetwothreefourfivesixseveneightnine";
        //System.out.println(originalDigits(s));
        //s = "onetwothreethreefourfour";
        System.out.println("我的:" + originalDigits(s));
        System.out.println("答案:" + originalDigits_v1(s));
    }

    /**
     * 0-9:zero，one，two，three，four，five，six ，seven，eight，nine
     * 找特殊字符
     * 一、从偶数开始(0 2 4 6 8)
     * z    只在zero(0)出现
     * w    只在two(2)出现
     * u    只在four(4)出现
     * x    只在six(6)出现
     * g    只在eight(8)出现
     * 二、奇数(1 3 5 7 9)
     * h    只在three eight出现
     * f    只在five four出现
     * s    只在seven six出现
     * i    只在出现five six eight nine
     * n    只在one two seven nine出现
     * 更直观的方式
     * 数字\字   a b c d e f g h i j k l m n o p q r s t u v w x y z
     * zero             *                   *     *               *
     * one              *                 * *
     * two                                  *         *     *
     * three            *     *                   *   *
     * four               *                 *     *     *
     * five             * *     *                         *
     * six                      *                   *         *
     * seven            *                 *         *     *
     * eight            *   * * *                      *
     * nine             *       *         *
     *
     * @param s
     * @return
     */
    public static String originalDigits(String s) {
        int[] counts = new int['a' + 26];
        /**
         * 步骤一：先统计各个字符的个数
         */
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i)]++;
        }
        /**
         * 步骤二：根据数字字符串特殊字符，依次根据统计的结果计算对应的数字
         */
        int[] arr = new int[10];
        // 只要出现'z'，绝对是one
        arr[0] = counts['z'];
        // 只要出现'w'，绝对是two
        arr[2] = counts['w'];
        // 只要出现'u'，绝对是four
        arr[4] = counts['u'];
        // 只要出现'x'，绝对是six
        arr[6] = counts['x'];
        // 只要出现'w'，绝对是two
        arr[8] = counts['g'];
        /**
         * 下面的思路：
         * eg 比如字符串：threeeight,'h'出现2次，
         * 由于有特殊'z'字符，所以一定有eight,这里会消耗一个'h'
         * 那么剩下一个'h'绝对属于three
         */
        // 出现'h'，可能是three eight，由于'h'个数固定，所以需要减去eight中消耗的'h'的个数，剩下就是three了
        arr[3] = counts['h'] - arr[8];
        // 出现'f'，可能是four five，由于'f'个数固定，所以需要减去four中消耗的'f'的个数，剩下就是five了
        arr[5] = counts['f'] - arr[4];
        // 出现's'，可能是seven six，由于's'个数固定，所以需要减去six中消耗的's'的个数，剩下就是seven了
        arr[7] = counts['s'] - arr[6];
        // 出现'i'，可能是five six eight nine，由于'i'个数固定，所以需要减去five six eight中消耗的'i'的个数，剩下就是nine了
        arr[9] = counts['i'] - arr[5] - arr[6] - arr[8];
        // 出现'n'，可能是one seven nine，由于'n'个数固定，所以需要减去seven nine中消耗的'n'的个数，剩下就是one了
        arr[1] = counts['n'] - arr[7] - arr[9] * 2; // 注意：nine消耗两个'n'
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i] && arr[i]>0; j++) {
                sb.append(i);
            }
        }
        return sb.toString();
    }


    /**
     * @param s
     * @param s
     * @return
     */
    public static String originalDigits_v1(String s) {
        // building hashmap letter -> its frequency
        char[] count = new char[26 + (int) 'a'];
        for (char letter : s.toCharArray()) {
            count[letter]++;
        }

        // building hashmap digit -> its frequency
        int[] out = new int[10];
        // letter "z" is present only in "zero"
        out[0] = count['z'];
        // letter "w" is present only in "two"
        out[2] = count['w'];
        // letter "u" is present only in "four"
        out[4] = count['u'];
        // letter "x" is present only in "six"
        out[6] = count['x'];
        // letter "g" is present only in "eight"
        out[8] = count['g'];
        // letter "h" is present only in "three" and "eight"
        out[3] = count['h'] - out[8];
        // letter "f" is present only in "five" and "four"
        out[5] = count['f'] - out[4];
        // letter "s" is present only in "seven" and "six"
        out[7] = count['s'] - out[6];
        // letter "i" is present in "nine", "five", "six", and "eight"
        out[9] = count['i'] - out[5] - out[6] - out[8];
        // letter "n" is present in "one", "nine", and "seven"
        out[1] = count['n'] - out[7] - 2 * out[9];

        // building output string
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output.append(i);
        return output.toString();
    }

}
